class Solution:

    def numberOfWays(self, n: int, x: int) -> int:
        a = 1
        while pow(a, x) <= n:
            a += 1
        f = [[0] * (n + 1) for _ in range(a)]
        for i in range(1, a):
            p = pow(i, x)
            f[i][p] = 1
            for j in range(1, i):
                for t in range(n + 1 - p):
                    if f[j][t] != 0:
                        f[i][t + p] += f[j][t]
        ans = 0
        for i in range(a):
            ans += f[i][n]
        return ans % 1000000007


class Solution:

    def numberOfWays(self, n: int, x: int) -> int:
        a = 1
        while pow(a, x) <= n:
            a += 1
        f = [0] * (n + 1)
        for i in range(1, a):
            p = pow(i, x)
            q = f.copy()
            q[p] += 1
            for j in range(n + 1 - p):
                q[j + p] += f[j]
            f = q
        return f[n] % 1000000007


class Solution:

    def numberOfWays(self, n: int, x: int) -> int:
        a = 1
        while pow(a, x) <= n:
            a += 1
        f = [0] * (n + 1)
        for i in range(1, a):
            p = pow(i, x)
            for j in range(n - p, -1, -1):
                f[j + p] += f[j]
            f[p] += 1
        return f[n] % 1000000007


s = Solution()
print(s.numberOfWays(n=10, x=2) == 1)
print(s.numberOfWays(n=4, x=1) == 2)
print(s.numberOfWays(n=300, x=1) == 872471266)
print(s.numberOfWays(n=275, x=1))
